package org.leetcode.middle.leetcode93;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution {

    List<String> res = new ArrayList<>();

    StringBuilder temp = new StringBuilder();

    int count = 0;

    public List<String> restoreIpAddresses(String s) {
        if (s.length()>12 || s.length()<4){
            return res;
        }
        backtracking(s,0,0);
        return res;
    }

    private void backtracking(String s,int index,int partCount) {
        if (partCount==4 && index==s.length()){
            res.add(new String(temp));
            return;
        }

        if (partCount==4 || index==s.length()){
            return;
        }

        for (int len = 1; len <=3 && index+len<=s.length(); len++) {
                String str = s.substring(index,index+len);
                if (isValidPart(str)){
                    int preLength = temp.length();
                    if (partCount>0){
                        temp.append(".");
                    }
                    temp.append(str);
                    partCount++;

                    backtracking(s,index+len,partCount);

                    temp.delete(preLength,temp.length());
                    partCount--;
                }
        }
    }


    private boolean isValidPart(String str){
        if (str.length()>1 && str.startsWith("0")){
            return false;
        }

        int val = Integer.valueOf(str);

        if (val<=255 && val>=0){
            return true;
        }
        return false;
    }

    private boolean isIp(String s, int startIndex, int endIndex) {
        String str = s.substring(startIndex, endIndex + 1);

        Integer num = Integer.getInteger(str);
        if (num >= 0 && num <= 255) {
            return true;
        } else {
            return false;
        }
    }
}
